package com.sourcetrip.algorithm.inter;

/**
 * @author: ZhouBert
 * @date: 2021/1/5
 * @description:	并查集（union find）接口
 * 为了解决特定问题的特殊接口：
 * 1.快速查找某个元素所属的集合；
 * 2.快速合并两个元素到相同的集合。
 * --
 * 设计：
 * 对外提供三个接口
 * --
 * 类似 二叉堆的思想，特定的数据结构只为 解决特定的问题
 * --
 * 回顾：
 * 并查集（UnionFind）的优化路线：
 * QuickFind (时间复杂度太高，舍弃)
 * QuickUnion （完成树化）-> 灵巧求并算法（【按大小求并】/【按高度(秩-rank)求并】-此算法更加合理）
 *	-> 路径压缩算法（Path Compression）/路径分裂（Path Splitting）/路径（可以与 按大小求并 兼容；但是与 按rank 求并 不兼容）
 * 那么不兼容怎么办呢：
 * 路径压缩不完全与按高度求并兼容，因为路径压缩可以改变树的高度。
 * 我们根本不清楚如何有效地去重新计算它们。答案就是不去计算！
 * 此时，对于每棵树所存储的高度就变成了估计的高度（有时称为秩(rank)），
 * 但实际上按秩求并(union by rank)（它正是现在已经变成的样子）理论上和按大小求并效率是一样的。
 * 不仅如此，高度的更新也不如大小的更新频繁。
 * 写按大小求并一样，我们也不清楚路径压缩平均是否值得。
 * 下一节将证明，两种求并试探法无论使用哪一种，都能使路径压缩显著地减少最坏情形运行时间。
 *
 * 作者：关小白
 * 链接：https://www.zhihu.com/question/379594680/answer/1432591115
 * 来源：知乎
 *
 * ——说明看起来按高度更符合查找优化，但是理论上与大小差不多。似乎由于高度实在无关紧要了，所以索性不去管了。
 */
public interface UnionFind {

	/**
	 * 查找v所属的集合（根节点）
	 * @param v
	 * @return
	 */
	int find(int v);

	/**
	 * 合并v1、v2所在的集合
	 */
	void union(int v1, int v2);

	/**
	 * 检查v1、v2是否属于同一个集合
	 */
	boolean isSame(int v1, int v2);
}
